/*
 * Add Binary
Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".
 */
package com.xinpan.exercise;

public class AddBinary {
    public String addBinary(String a, String b) {
        // Start typing your Java solution below
        // DO NOT write main() function
        String res = "";
        int forward = 0;
        int ai, bi;
        for(ai = a.length()-1, bi = b.length()-1; ai >=0 && bi >=0; ai--, bi--)
        {
            int sum = a.charAt(ai) - '0' + b.charAt(bi) - '0' + forward;
            forward = sum / 2;
            res = sum % 2 + res;
        }
        
        String left;
        if(ai < 0 && bi < 0)
        {
            if(forward == 1)
                return 1 + res;
            else 
                return res;
        }
        else if(ai < 0)
            left = b.substring(0, bi + 1);
        else
            left = a.substring(0, ai + 1);
        
        for(int lefti = left.length()-1; lefti >= 0; lefti--)
        {
            int sum = left.charAt(lefti) - '0' + forward;
            forward = sum/2;
            res = sum % 2 + res;
        }
        
        if(forward == 1)
            res = 1 + res;
        
        return res;
    }
    
    public static void main(String[] args)
    {
    	AddBinary addB = new AddBinary();
    	String res = addB.addBinary("11", "1");
    	System.out.println(res);
    }
}
